A sensor network is formed by a collection of tiny sensor nodes. Each sensor node typically includes a sensing device, a processor, and a wireless network interface. With those components, sensor nodes not only sense the surroundings at their neighborhoods independently but also exchange their sensed data and even process data for specific purposes. In order to efficiently store and query the sensed data, data-centric storage (DCS) in the sensor network has been studied.
In the DCS using geographic routing, since each node does not separately compose state information such as a routing table, it is possible to implement an efficient and scalable DOS.
DOS sensor network base on the geographic routing maps information on an event occurring at a specific sensor node to an arbitrary geographic location. The mapping is performed by hashing a name of the event or some attribute representing the event with a hash function such as SHA-1.
The event is stored at the closest neighboring node to the point where the hash value of the event indicates, which is called a rendezvous node. A query node interested in specific event information detects the rendezvous node storing the specific event and directly receives data therein without flooding a query over the entire network so as to find the rendezvous node storing the specific event. Those nodes which attempt to store an event or to query and retrieve a specific event hash a name or attributes of the corresponding event with a hash function, which is shared among network nodes, to discover the location of a rendezvous node including the event. Then, the nodes can send the event or the query to the rendezvous node and thereby to store the event at the rendezvous node or obtain the event from the rendezvous node. At this time, since destination of a packet is represented as geographic location, the packet is sent to a rendezvous node using geographic routing.
Greedy Perimeter Stateless Routing (GPSR) as a typical geographic routing algorithm is used at all of the nodes participating in DOS. All nodes implementing GPSR know geographic locations of themselves and neighborhoods within radio transmission range. GPSR utilizes two forwarding modes, i.e., greedy forwarding mode and perimeter forwarding mode, and performs routing while switching the forwarding modes. Greedy forwarding mode uses a greedy-style forwarding algorithm. When a node has a data packet, it forwards the packet to a neighbor whose position is closest to the destination location. This concept of greedy forwarding mode is illustrated in FIG. 1. On receiving the packet, the neighbor repeats the forwarding procedure. The greedy mode, however, does not always work because a packet possibly encounters a network void at which the forwarding node is the closest node to the destination location among all nodes in its one-hop neighborhood. The node, thus, cannot find a next hope to send the packet. For example, as shown in FIG. 2, a node x does not have a neighboring node which is closer to a destination node D than itself. To recover from that deadlock situation, perimeter forwarding mode is used. Perimeter forwarding mode chooses the next hope according to the right hand rule: the first counterclockwise encountered neighbor is selected as the next hope, which is illustrated in FIG. 3. Perimeter forwarding mode routes the data packet along perimeter of the network void to escape from the deadlock situation at the network void. Greedy forwarding mode is resumed when the packet reaches to a node that is closer to the destination location than the entry node where perimeter forwarding mode starts. If the destination node is disconnected from the source, keeping forwarding packets with perimeter mode makes packets loop at nodes that are closest to the destination locations. In DCS sensor networks, since a destination location of an event is acquired by hashing a name or attributes of the event, and the hashed value may result in “empty” destination locations (location at which there are no nodes residing), disconnection between sources and destinations happen frequently. Consequently, packets frequently loop on perimeters containing destination location and form perimeter walks. FIG. 4 illustrates an example of perimeter walk.
Referring to FIG. 4, a data packet is routed from node S to an empty destination location T . The packet is, firstly, forwarded by greedy mode to node N. At the node N, the packet is switched to perimeter mode since there are no neighbors of N that are closer to T than N. The packet then circumnavigates on the perimeter of face M-N-O-P-Q and finally loops at N. A packet completes a perimeter walk only if it continuously visits every edge of a face with perimeter mode solely. Thus, the perimeter walk completes at node N.
As one property of a perimeter walk is that it always completes at the closest node to the corresponding destination location. If a packet, by perimeter forwarding, arrives at a node closer to the entry node where perimeter forwarding mode starts, the packet will fall back to greedy forwarding mode, and ongoing perimeter walk will be reset. Thus, perimeter walks never complete at nodes that are not closest to the destination location.
Existing geographic routing based DCS schemes utilize perimeter walks for identifying rendezvous nodes, nodes are closest to destination locations. Such perimeter walks, however, can cause considerable communication overhead in geographic routing protocols.